package com.mrzhou.study.struct.tree.binary;

/**
 *  树结构之二叉树
 *  二叉树的一些特征:
 *      每个节点最多有两颗子树, 所以二叉树中不存在度大于2的节点
 *      左子树和右子树是有顺序的, 次序不能任意颠倒
 *      即使树中某一节点只有一颗子树, 也要区分是左子树还是右子树
 */
public class BinaryTree<T> {

    private TreeNode<T> root; // 根节点

    public static void main(String[] args) {
        BinaryTree<String> binaryTree = BinaryTree.testTree();
        System.out.print("前序遍历: ");
        binaryTree.preOrder(binaryTree.root);
        System.out.print("\n前序搜索: ");
        System.out.println(binaryTree.preSearch("C",binaryTree.root));
        System.out.println();
        System.out.print("中序遍历: ");
        binaryTree.infixOrder(binaryTree.root);
        System.out.print("\n中序搜索: ");
        System.out.println(binaryTree.infixSearch("J", binaryTree.root));
        System.out.println();
        System.out.print("后序遍历: ");
        binaryTree.suffixOrder(binaryTree.root);
        System.out.print("\n后序搜索: ");
        System.out.println(binaryTree.suffixSearch("D", binaryTree.root));
        System.out.println();
    }

    /**
     * 前序遍历二叉树
     *  在第一次扫描到节点时，输出节点信息
     */
    public void preOrder(TreeNode<T> root) {
        System.out.print(root.data + " ---> ");
        if(root.leftNode != null) {
            preOrder(root.leftNode);
        }
        if(root.rightNode != null) {
            preOrder(root.rightNode);
        }
    }

    /**
     * 中序遍历二叉树
     *  在第二次扫描到节点时，输出节点信息
     */
    public void infixOrder(TreeNode<T> node) {
        if(node.leftNode != null) {
            infixOrder(node.leftNode);
        }
        System.out.print(node.data + " ---> ");
        if(node.rightNode != null) {
            infixOrder(node.rightNode);
        }
    }

    /**
     * 后序遍历二叉树
     *  在第三次扫描到节点时，输出节点信息
     */
    public void suffixOrder(TreeNode<T> node) {
        if(node.leftNode != null) {
            suffixOrder(node.leftNode);
        }
        if(node.rightNode != null) {
            suffixOrder(node.rightNode);
        }
        System.out.print(node.data + " ---> ");
    }

    /**
     * 前序遍历搜索树
     * @param <T> 返回查找的树节点
     * @return
     */
    public <T> TreeNode<T> preSearch(T data, TreeNode<T> root) {
        TreeNode<T> resultNode = null;
        if(root.data.equals(data)) { //判断当前接口
            return root;
        }
        // 左递归查询树是否有相等字节
        if(root.leftNode != null) {
            resultNode = preSearch(data, root.leftNode); // 查找结构树, 将搜索结果返回给零时变量
        }

        if(resultNode != null) { // 查找到, 则直接将节点数据放回
            return resultNode;
        }

        // 左递归为查找到, 开始进行右递归
        if(root.rightNode != null) {
            resultNode = preSearch(data, root.rightNode);
        }
        return resultNode;
    }

    /**
     * 中序遍历搜索树
     */
    public <T> TreeNode<T> infixSearch(T data, TreeNode<T> root) {
        TreeNode<T> resultNode = null;
        if(root.leftNode != null) {
            resultNode = infixSearch(data, root.leftNode);
        }
        if(resultNode != null) { // 左递归遍历完毕, 查找到则返回所在的树节点
            return resultNode;
        }

        if(root.data.equals(data)) { // 判断当前节点是否相同
            return root;
        }

        if(root.rightNode != null) { // 右递归查询树
            resultNode = infixSearch(data, root.rightNode);
        }
        return resultNode; //
    }

    /**
     * 后序遍历二叉树
     */
    public <T> TreeNode<T> suffixSearch(T data, TreeNode<T> root) {
        TreeNode<T> resultNode = null;
        if(root.leftNode != null) { // 递归遍历左节点
            resultNode = suffixSearch(data, root.leftNode);
        }
        if(resultNode != null) { // 不为空则表示查找到节点
            return resultNode;
        }
        if(root.rightNode != null) { // 右节点遍历树
            resultNode = suffixSearch(data, root.rightNode);
        }
        if(root.data.equals(data)) {
            return root;
        }
        return resultNode;
    }

    /**
     * 删除保存指定数据的节点
     */
//    public boolean delTreeNode(T data, TreeNode<T> root) {
//
//    }

    /**
     *
     * @return
     */
    public boolean isEmpty() {
        return root ==null || (this.root.leftNode == null && root.rightNode == null && root.data == null);
    }

    /**
     * 构建一个测试数, 二叉树的逻辑结构见: classpath: images/二叉树-001.png
     */
    public static BinaryTree<String> testTree() {
        BinaryTree<String> tree = new BinaryTree<>();

        TreeNode<String> aNode = new TreeNode<>("A");
        TreeNode<String> bNode = new TreeNode<>("B");
        TreeNode<String> cNode = new TreeNode<>("C");
        TreeNode<String> dNode = new TreeNode<>("D");
        TreeNode<String> eNode = new TreeNode<>("E");
        TreeNode<String> fNode = new TreeNode<>("F");
        TreeNode<String> gNode = new TreeNode<>("G");
        TreeNode<String> hNode = new TreeNode<>("H");
        TreeNode<String> iNode = new TreeNode<>("I");
        TreeNode<String> jNode = new TreeNode<>("J");

        tree.root = aNode;
        aNode.leftNode = bNode;
        aNode.rightNode = cNode;
        bNode.leftNode = dNode;
        bNode.rightNode = eNode;
        cNode.leftNode = fNode;
        cNode.rightNode = gNode;
        dNode.leftNode = hNode;
        dNode.rightNode = iNode;
        eNode.leftNode = jNode;
        return tree;
    }

}
